home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / PET / S-Super PET / (s)t4.d64 / KNIGHTS_TOUR.BAS < prev    next >
BASIC Source File  |  2009-01-18  |  2KB  |  92 lines
  1.    10 ! Knight's Tour
  2.    20 ! by Jack Schueler
  3.    30 !    Waterloo Computing Systems Limited
  4.    40 !    Waterloo, Ontario, Canada
  5.    50 
  6.    60 ! This program attempts to find a tour of the chess board
  7.    70 ! using the knight's move to cover all squares once and
  8.    80 ! only once. The algorithm used is a heuristic. Given a
  9.    90 ! sufficient amount of time (sometimes megayears) it will
  10.   100 ! find a solution. Fortunately solutions to some starting
  11.   110 ! positions are found fairly quickly. Try 4,3; it's quick.
  12.   120 
  13.   130 dim istack%(64),jstack%(64),dstack%(64),board%(11,11)
  14.   140 dim di%(11),dj%(11)
  15.   150 data  2, 1,-1,-2,-2,-1, 1, 2, 2, 1,-1,-2
  16.   160 data -1,-2,-2,-1, 1, 2, 2, 1,-1,-2,-2,-1
  17.   170 mat read di%, dj%
  18.   180 mat board% = (-1)
  19.   190 for i% = 2 to 9
  20.   200   for j% = 2 to 9
  21.   210     board%(i%,j%) = 0
  22.   220   next j%
  23.   230 next i%
  24.   240 print 'Enter the starting position (1,1 is the top left corner)'
  25.   250 input i%, j%
  26.   260 call drawboard
  27.   270 i% = i% + 1
  28.   280 j% = j% + 1
  29.   290 d% = -1
  30.   300 sp% = 1
  31.   310 loop 
  32.   320   offset% = 4 * (i% <= j%)
  33.   330   guess 
  34.   340     loop 
  35.   350       d% = d% + 1
  36.   360       if d% = 8 then 500
  37.   370       ti% = i% + di%(d% + offset%)
  38.   380       tj% = j% + dj%(d% + offset%)
  39.   390     until board%(ti%,tj%) = 0
  40.   400     istack%(sp%) = i%
  41.   410     jstack%(sp%) = j%
  42.   420     dstack%(sp%) = d%
  43.   430     board%(i%,j%) = sp%
  44.   440     x$=fnp$(i%,j%,sp%)
  45.   450     i% = ti%
  46.   460     j% = tj%
  47.   470     sp% = sp% + 1
  48.   480     d% = -1
  49.   490   admit 
  50.   500     sp% = sp% - 1
  51.   510     board%(i%,j%) = 0
  52.   520     x$=fnp$(i%,j%,0)
  53.   530     i% = istack%(sp%)
  54.   540     j% = jstack%(sp%)
  55.   550     d% = dstack%(sp%)
  56.   560   endguess 
  57.   570 until sp% = 64
  58.   580 board%(i%,j%) = 64
  59.   590 x$=fnp$(i%,j%,64)
  60.   600 x$=fnw$(0,23,"")
  61.   610 x=cursor(1)
  62.   620 stop 
  63.   630 proc drawboard
  64.   640   print chr$(12)
  65.   650   x$=rpt$("!     ",8)+"!"
  66.   660   y$=rpt$("-",49)
  67.   670   for row% = 0 to 22
  68.   680     if mod(row%,3) <> 2
  69.   690       z$=fnw$(12,row%,x$)
  70.   700     else 
  71.   710       z$=fnw$(12,row%,y$)
  72.   720     endif 
  73.   730   next row%
  74.   740 endproc 
  75.   750 def fnw$( col%, row%, ch$ )
  76.   760   pos% = row%*80 + col% + 1
  77.   770   pos=cursor(pos%)
  78.   780   print ch$;
  79.   790   fnw$=ch$
  80.   800 fnend 
  81.   810 def fnp$( i%, j%, s% )
  82.   820   i% = i% - 2
  83.   830   j% = j% - 2
  84.   840   if s% = 0
  85.   850     x$=fnw$(14+6*j%, 3*i%, "   ")
  86.   860   else 
  87.   870     x$=fnw$(14+6*j%, 3*i%, value$(s%) )
  88.   880   endif 
  89.   890   fnp$=""
  90.   900 fnend 
  91.   910 end 
  92.